package com.li.sort.arithmetic;

import java.util.Arrays;
import java.util.Random;

public class RadixSort {
	public static final int SIZE = 10000000;
	public static void main(String[] args) {
		int[] array = new int[SIZE];
		Random random = new Random();
		for(int i = 0;i < SIZE ;i++){
			array[i] = random.nextInt(100);
		}
		
		//System.out.println(Arrays.toString(array));
		long time1= System.currentTimeMillis();
		radixSort(array,getMaxLength(array));
		System.out.println(System.currentTimeMillis()-time1);
		//System.out.println(Arrays.toString(array));
	}
	
	/**
	 * n-1趟排序就ok
	 * @param array
	 */
	public static void radixSort(int[] array,int n){
		int[][] tempArray = new int[10][array.length+1];
		for(int i = 1;i <= n;i++){
			for(int j=0;j<array.length;j++){
				int row  = getNumInpos(array[j], i);
				int col = ++tempArray[row][0];
				tempArray[row][col] = array[j];
			}
			for(int row =0,j=0;row<10;row++){
				for(int col=1;col<=tempArray[row][0];col++){
					array[j++] = tempArray[row][col];
				}
				tempArray[row][0]=0;
			}
		}
	}
	
	public static void swap(int[] array,int i,int j){
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
	
	public static int getMaxLength(int[] array){
		int count = 1;
		int max = 0;
		int temp;
		for(int i =1;i<array.length;i++){
			if(array[i]>array[max]){
				max = i;
			}
		}
		temp = array[max];
		while((temp/=10) !=0){
			count++;
		}
		return count;
	}
	
	public static int getNumInpos(int num,int pos){
		int temp = 1;
		for(int i=0;i < pos-1;i++){
			temp*=10;
		}
		return (num/temp)%10;
	}
}
